1. Field of the Invention
The present invention relates to an admission control scheme for multimedia streams on an integrated network and, more particularly, to a method and apparatus for predicting whether or not to admit multimedia streams on an integrated network.
2. Description of the Related Art
Multimedia services require some combination of text, image, voice and video storage, and communication. Such multimedia services have potential applications in many areas, including medical imaging, education, banking, advertising and publishing.
Since integrated networks are capable of supporting a variety of multimedia services, they are presently being heavily researched for multimedia applications. Integrated networks support digital telephony, multimedia and data communications in an integrated fashion. An example of an integrated network is Broadband Integrated Services Digital Networks (BISDN).
Generally speaking, integrated networks are designed to allow both data and multimedia services to coexist. Data services, which are also termed best-efforts, are bursty and, for the most part, unpredictable. Therefore, in order to guarantee the performance requirements of real-time traffic, it is necessary to isolate real-time traffic from best-effort data.
Multimedia applications that integrate digital audio and video (among other media types) require certain traffic guarantees to achieve the performance which users of analog television systems are accustomed. These guarantees include that there will be sufficient bandwidth to accommodate the largest peaks transmitted; that there will be a small, constant end-to-end delay; and that there will be an upper bound (usually very small) on the probability of data loss. Other guarantees may be needed, for example, media synchronization, but these other guarantees can be provided by other components of a networked multimedia system.
Clearly, conventional data networks, with their emphasis on resource sharing and reactive congestion-control mechanisms, are woefully incapable of supporting real-time services. For example, the conventional protocol in data networks is to simply resend information when packets are lost or a data queue has overflowed due to congestion. Although this protocol might be acceptable for general data communications, it is totally unacceptable for real-time or interactive multimedia applications.
Furthermore, because of the timing requirements of multimedia applications, it is unacceptable to control admission of requests by admitting a new request tentatively, and then terminating the request if performance guarantees for the existing connections cannot be satisfied. For example, if the admission request were a movie, the movie would begin and then abruptly end, thereby frustrating the viewer.
In any event, conventional data networks fail on all counts because they cannot provide any of the three types of guarantees listed above. As a result, there has been a shift to rate-based, connection-oriented communication. Since real-time streams are rate limited, a network can try to set aside enough resources to handle the requests for guaranteed service before communication begins.
Before admitting a multimedia application to a network and allowing it to transmit, the network will require the application to declare its performance requirements and the traffic that it will produce. Using this specification, the network assesses whether it has sufficient resources to guarantee that tile application's requirements can be satisfied, and a connection established, hopefully without violating the requirements of any of the existing connections. Only then is the application allowed to transmit.
The nature of the performance guarantees that networks must provide can be classified into two broad categories: hard real-time guarantees when the requirements of an admitted application will never be violated, and soft real-time guarantees when the network will occasionally, but infrequently, violate the application's requirements. When providing hard real-time service, the network guarantees apply irrespective of the behavior of all other applications that will be simultaneously using the network. Consequently, when hard real-time guarantees are required, admission control must be based on the worst-case behavior of each individual connection. Furthermore, either the network switching equipment must isolate the various connections from one another so that they have exclusive use of the resources that have been assigned to them, or resource reservation at admission-control time must be done explicitly on a per connection basis. Worst-case resource allocation and isolation of resources often results in poor network utilization.
With soft-real time service, network resources are shared among a group of connections. The network cannot guarantee that the performance requirements of a group of connections will be continuously satisfied. Nevertheless, since soft real-time services avoid the worst-case design necessary for hard real-time services, soft real-time services will result in a much higher utilization of network resources than hard real-time services. However, the key to the successful deployment of soft real-time services on integrated networks will depend on the effectiveness of the admission-control scheme, which must be conservative enough to ensure that violations of applications' performance requirements are infrequent, while at the same time ensuring that the network is sufficiently utilized to make it economically competitive. Because resources are allocated to groups of connections, rather than to individual connections, soft real-time services offer the additional advantage of simplified network management. Specifically, resource managers need only allocate and administer pools of resources tier each of the groups that share them, rather than for a multitude of individual connections. Furthermore, a soft-real time service may be the only viable service for multimedia traffic that can be supported on the first generation of asynchronous transfer mode (ATM) networks switches, which have a limited number of queues, typically two to four, per link.
In order to obtain performance guarantees, an application must translate its traffic requirements, possibly using an application programming interface, into network requirements, which are provided to the network through a service interface. The service interface also allows an application to specify the type and quality of guarantees that the application needs. There are typically three elements in a service interface: a traffic contract used by the application to describe the characteristics of the traffic it will produce; a set of objective values for Quality of Service (QoS) parameters that the network defines; and the type of commitment that is requested.
The traffic contract, which models the application's traffic, is used as a basis for making admission decisions. A commonly used model is in the form of a token-bucket descriptor, a two-parameter descriptor (r,b), in which r is the rate at which tokens accumulate in the token bucket and b is the capacity of the bucket. Tokens, which represent credits for units of transmission, overflow when the bucket is full, i.e., when it already contains b tokens. Thus, r is the average rate of the model and b is the maximum size of a burst that can be transmitted at once. The translation between the characteristics of a data stream produced by an application and the token-bucket model need not be performed by the application itself, but is likely to be offered as a system function by applications' libraries.
Performance guarantees are requested by providing objective values for the QoS parameters defined by the service interface. These parameters may include end-to-end delay and loss probability. Additional guarantees, such as delay-jitter bounds or synchronization guarantees, may be provided by higher layers of the network.
The third element of the service interface is used to indicate the service commitments, which may be implicit if a network provides only one class of commitments. Whereas the QoS parameters determine the type of service offered by the network to the application, the service commitment determines tile quality of tile requested service. As previously mentioned, service commitments provided by the network to multimedia real-time applications can be categorized into hard real-time guarantees and soft real-time guarantees.
Before a decision can be made about an application's request for admission, a network's routing subsystem must find a path from source to destination. Without cooperation from the routing subsystem (e.g., routers), a network's ability to support real-time traffic is greatly impaired. In order to choose among potential paths for routing application requests, the routing subsystem usually requires information about the status of all network links and associated switching nodes. This information must be provided by network managers implemented at each of the network nodes. Admission control is, however, still necessary since in some cases the routing subsystem's choice may not be up-to-date.
Admission control need not rely on routing for making admission decisions. However, since the choice of the path along which the application request will attempt to establish a connection is determined by a routing algorithm, the effectiveness of admission control (measured in terms of the numbers of admitted requests, the number of incorrect admissions, etc.) will be dependent on the intelligence built into the routers. A naive routing algorithm may thwart the effectiveness of any admission-control scheme. For example, it is easy to construct an example in which a routing algorithm that only routes requests over the shortest path will saturate that path resulting in unbalanced link utilization and high real-time call blocking probability.
Several known admission-control schemes do not require that routes be chosen according to the requested guarantees. Clark et al., Supporting Real-Time Applications in an Integrated Services Packet Network, Proceedings of ACM SIGCOMM, August 1992, pp. 14-26, describes a predictive service that does not depend on routing and that may still be acceptable because it is designed for adaptive applications whose initial QoS bounds are relaxed. Ferrari et al., A Scheme for Real-Time Channel Establishment in Wide-Area Networks, IEEE Journal in Selected Areas in Communications, Vol. 8, No. 3, April 1990, pp. 368-379, at least in the initial description of the Tenet scheme, also do not support routing. They have recently indicated, however, that they may be able to support routing. Their scheme, however, which requires detailed switching-node and link information, seems to preclude an easy implementation of this feature. Known techniques that support policy-based routing are presently not directly related to network admission control, see Estrin et al., A Protocol for Route Establishment and Packet Forwarding Across Multimedia Across Multidomain Internets, IEEE/ACM Transaction on Networking, Vol. 1No. 1, February 1993, pp. 56-70.
To support real-time information, tile network must implement an admission control function. The admission control function is in charge of allocating network resources (bandwidth, buffer space, transmission scheduler time, etc.) in such a manner that the service commitments provided to all admitted connections are adhered to throughout the lifetime of the connections. Since a network has limited resources, the network must restrict the number of applications to which tile network can simultaneously provide service commitments. Admission control refers to the process of making decisions on whether or not a new application request can be admitted to the network based on the current status of the network and on the service requirements of the new request. A new application request is admitted if it satisfies the following two admission rules:
(1) The network is capable of providing the new connection with the service that the application requires. PA1 (2) The service commitments provided to existing connections will continue to be satisfied after tile new request is admitted.
Since admission control attempts to prevent the occurrence of congestion, admission-control is a proactive form of congestion control.
Known admission-control schemes have adopted contrasting methods for controlling admission of application requests to networks. A number of schemes have simulated target environments under different operating conditions and have utilized the data obtained from these simulations to make admission decisions in actual network environments. See Decina et al., Bandwidth Assignment and Virtual Call Blocking in ATM Networks, Proceedings of IEEE INFOCOM, May 1990, pp. 881-888; Gallassi et al., ATM: Bandwidth Assignment and Bandwidth Enforcement Policies, Proceedings of IEEE Globecom, 1989, pp. 1788-1793; Woodruff et al., Multimedia Traffic Management Principals for Guaranteed ATM Network Performance, IEEE Journal on Selected Areas in Communications, Vol. 8, No. 3, April 1990, pp. 437-446. The static nature of data obtained from simulations makes these schemes impractical for deployment in large-scale networks in which traffic and network characteristics may change dynamically. Alternatively, other schemes have relied on pre-specified information about the behavior of traffic sources provided as part of the traffic contract to derive analytical expressions that are used for making admission decisions, see Ferrari et al,, supra; Cidon et ai., Bandwidth Management and Congestion Control in plaNET, IEEE Communications Magazine, Vol. 29, No. 10, October 1991, pp. 54-64. There are several disadvantages with these schemes. First, the traffic descriptors are too elaborate requiring several different parameters (in contrast a leaky-bucket descriptor has only two parameters). Second, these schemes are independent of routing. Third, these schemes work efficiently only with a few switch scheduling disciplines. Finally, these schemes rely on worst-case assumptions and result in poor network utilization for the real-time class.
Technological advances are making it possible for integrated networks to support not only today's non-real-time applications, but also new multimedia applications that demand performance guarantees. Because performance guarantees such as bandwidth and delay-bounds cannot be provided by conventional reactive mechanisms for congestion control, improved traffic admission control techniques (proactive congestion-control mechanisms) are needed for real-time networks.
Thus there is a need for a novel, flexible admission control scheme to control admission of multimedia streams on an integrated network.